Bubble Sort Nedir?
Bubble Sort (Kabarcık Sıralama), en basit sıralama algoritmalarından biridir. Adını, sıralama sırasında büyük değerlerin dizinin sonuna doğru "kabarcık gibi yükselmesi" prensibinden alır.
Nasıl Çalışır?
Algoritma, yan yana olan elemanları karşılaştırarak ve gerekirse yer değiştirerek çalışır:
- Dizinin başından başlayarak, her elemanı bir sonraki eleman ile karşılaştırır.
- Eğer mevcut eleman sonraki elemandan büyükse, yerlerini değiştirir.
- Bu işlemi dizinin sonuna kadar devam ettirir.
- Her geçişin sonunda, en büyük eleman dizinin sonuna yerleşmiş olur.
- Bu işlemi tüm dizi sıralanana kadar tekrarlar.
// Bubble Sort Algoritması - JavaScript
function bubbleSort(array) {
const n = array.length;
for (let i = 0; i < n - 1; i++) {
// Her geçişte, dizinin (n-i-1) elemanını kontrol ediyoruz
for (let j = 0; j < n - i - 1; j++) {
// Eğer mevcut eleman sonraki elemandan büyükse
if (array[j] > array[j + 1]) {
// Elemanların yerlerini değiştir
[array[j], array[j + 1]] = [array[j + 1], array[j]];
}
}
}
return array;
}
Kararlılık (Stability)
Bubble Sort, kararlı (stable) bir sıralama algoritmasıdır. Bu, aynı değere sahip elemanların sıralamadan önce ve sonra aynı göreceli sırada kaldığı anlamına gelir.
Örneğin, [5, 1, 4, 5*, 2] (5* ile işaretli eleman farklı bir öğe olarak düşünün) dizisini sıraladığınızda, iki adet 5 değeri orijinal sırada kalır, yani [1, 2, 4, 5, 5*] şeklinde olur, 5* değeri ikinci 5 olarak kalır.
Zaman ve Uzay Karmaşıklığı
Zaman Karmaşıklığı:
- En İyi Durum: O(n) - Dizi zaten sıralı ise
- Ortalama Durum: O(n²)
- En Kötü Durum: O(n²) - Dizi ters sıralı ise
Uzay Karmaşıklığı: O(1) - Sabit ek alan kullanır
Avantajları ve Dezavantajları
Avantajları:
- Basit ve anlaşılması kolay bir algoritma
- Kararlı bir sıralama algoritması
- Ek bellek gereksinimi yoktur (yerinde sıralama yapar)
- Küçük veri setlerinde kabul edilebilir performans gösterir
Dezavantajları:
- Büyük veri setlerinde verimsizdir
- Selection Sort ve Insertion Sort gibi diğer basit algoritmalardan genellikle daha yavaştır
Kullanım Alanları
Bubble Sort, aşağıdaki durumlarda tercih edilebilir:
- Eğitim amaçlı - Sıralama algoritması kavramlarını öğrenmek için mükemmel bir başlangıç noktasıdır
- Küçük veri setleri - Az sayıda elemanı olan listeler
- Zaten neredeyse sıralı olan veri setleri
- Bellek kısıtlaması olan sistemlerde (ek bellek gerektirmez)
- Donanım uygulamaları - Basit olması nedeniyle bazı gömülü sistemlerde tercih edilebilir